class Node {
    constructor(key = null, value = null) {
        this.key = key
        this.value = value
        this.left = null
        this.right = null
        this.height = 1
    }
}

export class AVLTree {
    constructor() {
        this.root = null
        this.size = 0
    }

    getSize() {
        return this.size
    }

    isEmpty() {
        return this.size === 0
    }

    isBST() {
        const keys = []
        this.inOrder(this.root, keys)
        for (let i = 0; i < keys.length; i++) {
            if (keys[i - 1] > keys[i]) {
                return false
            }
        }
        return true
    }

    inOrder(node, keys) {
        if (node === null) return

        this.inOrder(node.left, keys)
        keys.push(node.key)
        this.inOrder(node.right, keys)
    }

    isBalanced() {
        return this._isBalanced(this.root)
    }

    _isBalanced(node) {
        if (node === null) {
            return true
        }

        const balanceFactor = this.getBalanceFactor(node)
        if (Math.abs(balanceFactor) > 1) {
            return false
        }
        return this._isBalanced(node.left) && this._isBalanced(node.right)
    }

    getHeight(node) {
        if (node === null) {
            return 0
        }
        return node.height
    }

    getBalanceFactor(node) {
        if (node === null) {
            return 0
        }
        return this.getHeight(node.left) - this.getHeight(node.right)
    }

    //             y
    //           /  \
    //         x    T4
    //       /  \
    //     z    T3
    //   / \
    // T1  T2
    rightRotate(y) {
        const x = y.left
        const T3 = x.right

        x.right = y
        y.left = T3

        y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1
        x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1

        return x
    }

    leftRotate(y) {
        const x = y.right
        const T2 = x.left

        x.left = y
        y.right = T2

        y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1
        x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1

        return x
    }

    add(key, value) {
        this.root = this._add(this.root, key, value)
    }

    _add(node, key, value) {
        if (node === null) {
            this.size++
            return new Node(key, value)
        }

        if (node.key > key) {
            node.left = this._add(node.left, key, value)

        } else if (node.key < key) {
            node.right = this._add(node.right, key, value)

        } else {
            node.value = value

        }

        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right))

        const balanceFactor = this.getBalanceFactor(node)

        // LL
        if (balanceFactor > 1 && this.getBalanceFactor(node.left) >= 0) { // 不平衡
            return this.rightRotate(node)
        }

        // RR
        if (balanceFactor < -1 && this.getBalanceFactor(node.right) <= 0) { // 不平衡
            return this.leftRotate(node)
        }

        // LR
        if (balanceFactor > 1 && this.getBalanceFactor(node.left) < 0) { // 不平衡
            node.left = this.leftRotate(node.left)
            return this.rightRotate(node)
        }

        // RL
        if (balanceFactor < -1 && this.getBalanceFactor(node.right) > 0) { // 不平衡
            node.right = this.rightRotate(node.right)
            return this.leftRotate(node)
        }

        return node
    }

    getNode(node, key) {
        if (node === null) {
            return null
        }

        if (key === node.key) {
            return node

        } else if (key < node.key) {
            return this.getNode(node.left, key)

        } else {
            return this.getNode(node.right, key)

        }
    }

    contains(key) {
        return this.getNode(this.root, key) !== null
    }

    get(key) {
        const node = this.getNode(this.root, key)
        return node === null ? null : node.value
    }

    set(key, value) {
        const node = this.getNode(this.root, key)
        if (node === null) {
            throw new Error(`${key} doesn't exist!`)
        }
        node.value = value
    }

    remove(key) {
        const node = this.getNode(this.root, key)

        if (node !== null) {
            this.root = this._remove(this.root, key)
            return node.value
        }

        return null
    }

    _remove(node, key) {
        if (node === null) {
            return null
        }

        let retNode = null
        if (key < node.key) {
            node.left = this._remove(node.left, key)
            retNode = node

        } else if (key > node.key) {
            node.right = this._remove(node.right, key)
            retNode = node

        } else { // if (key === node.key)

            if (node.left === null) {
                const rightNode = node.right
                node.right = null
                this.size--
                retNode = rightNode

            } else if (node.right === null) {
                const leftNode = node.left
                node.left = null
                this.size--
                retNode = leftNode

            } else {
                // 待删除节点左右子树均不为空的情况
                // 找到比删除节点大的最小节点，即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                const successor = this._minimum(node.right)
                successor.right = this.remove(node.right)
                successor.left = node.left

                node.left = node.right = null
                retNode = successor

            }
        }

        if (retNode === null) {
            return null
        }

        retNode.height = 1 + Math.max(this.getHeight(retNode.left), this.getHeight(retNode.right))

        const balanceFactor = this.getBalanceFactor(retNode)

        // LL
        if (balanceFactor > 1 && this.getBalanceFactor(retNode.left) >= 0) { // 不平衡
            return this.rightRotate(retNode)
        }

        // RR
        if (balanceFactor < -1 && this.getBalanceFactor(retNode.right) <= 0) { // 不平衡
            return this.leftRotate(retNode)
        }

        // LR
        if (balanceFactor > 1 && this.getBalanceFactor(retNode.left) < 0) { // 不平衡
            retNode.left = this.leftRotate(retNode.left)
            return this.rightRotate(retNode)
        }

        // RL
        if (balanceFactor < -1 && this.getBalanceFactor(retNode.right) > 0) { // 不平衡
            retNode.right = this.rightRotate(retNode.right)
            return this.leftRotate(retNode)
        }

        return retNode
    }

    minimum() {
        if (this.size === 0) {
            throw new Error('BST is empty.')
        }

        return this._minimum(this.root).val
    }

    _minimum(node) {
        if (node.left === null) {
            return node
        }

        return this._minimum(node.left)
    }

    maximum() {
        if (this.size === 0) {
            throw new Error('BST is empty.')
        }

        return this._maximum(this.root).val
    }

    _maximum(node) {
        if (node.right === null) {
            return node
        }

        return this._maximum(node.right)
    }

    removeMin() {
        const min = this.minimum()
        this.root = this._removeMin(this.root)
        return min
    }

    _removeMin(node) {
        if (node.left === null) {
            const rightNode = node.right
            node.right = null
            this.size--
            return rightNode
        }

        node.left = this._removeMin(node.left)
        return node
    }

    removeMax() {
        const max = this.maximum()
        this.root = this._removeMax(this.root)
        return max
    }

    _removeMax(node) {
        if (node.right === null) {
            const leftNode = node.left
            node.left = null
            this.size--
            return leftNode
        }

        node.right = this._removeMax(node.right)
        return node
    }
}